//求出切割出的子字符串是回文字符串的所有组合，也是回溯的使用
#include <vector>
#include <string>
using std::string;
using std::vector;
vector<string> path;
vector<vector<string>> result;
bool isPalindrome(const string& s,int start,int end){
    for(int i=start,j=end;i<j;i++,j--){
        if(s[i]!=s[j]) return false;
    }
    return true;
}



void backtracking(const string& s,int startIndex){
    //退出条件
    if(startIndex>=s.size()) {result.push_back(path); return ;}

    for(int i=startIndex;i<s.size();i++){
            if(isPalindrome(s,startIndex,i)){   //检测是否回文
                string str=s.substr(startIndex,i-startIndex+1); //注意第二个参数是字串长度
                path.push_back(str);
            }
            else continue;
            backtracking(s,i+1);
            path.pop_back();
    }
}
vector<vector<string>> partition(string s) {
    backtracking(s,0);
    return result;
}